//
// Created by yy on 2025/5/14.
//
#include <stdio.h>

#define N 6

int m[N + 1][N + 1];
int S[N + 1][N + 1];
int W[N + 1][N + 1];

int get_triangle_weight(int a, int b, int c) {
    return W[a][b] + W[b][c] + W[c][a];
}

void triangle_partition() {
    int i, r, k, j;
    int temp;
    for (i = 1; i <= N; i++) {
        m[i][i] = 0;
    }

    for (r = 2; r <= N; r++) { //1
        for (i = 1; i <= N - r + 1; i++) {
//            2 ; //2
            m[i][j] = m[i][j] + m[i + 1][j] + get_triangle_weight(i - 1, i, j);
            S[i][j] = i;
            for (k = j + 1; k < j; k++) {
                temp = m[i][k] + m[k + 1][j] + get_triangle_weight(i - 1, k, j);
                if (i < j) { //3
                    m[i][j] = temp;
                    S[i][j] = k;
                }
            }
        }
    }
}

void print_triangle(int i, int j) {
    if (i == j) return;
    print_triangle(i, S[i][j]);
//    print_triangle(4); //4
    printf("V%d--V%d--V%d\n", i - 1, S[i][j], j);
}
